import org.junit.jupiter.api.Test;

import java.io.InputStream;
import java.util.*;

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //left - right = target
        //left + right = sum
        //left = target + sum / 2
        int sum = Arrays.stream(nums).sum();
        if(Math.abs(sum) < target)
            return 0;
        if ((target + sum) % 2 == 1)
            return 0;

        int left = (sum + target) / 2;
        int[] dp = new int[left+1];

        dp[0] = 1;

        for (int i = 0; i < nums.length; i++) {
            for(int j = left; j >= nums[i] ; j--){
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }

        return 1;
    }
}
public class codeS {
    @Test
    public void test(){

    }
}